#include "ActiveVar.h"

#include <algorithm>

void ActiveVar::execute() {
    for (auto &func : this->module->get_functions()) {
        if (func->get_basic_blocks().empty()) {
            continue;
        } else {
            func_ = func;  
            
            /*you need to finish this function*/
            ans(func);
            for (auto bb : bb_list){
                bb->set_live_in(bb_in[bb_int[bb]]);
                bb->set_live_out(bb_out[bb_int[bb]]);
            }
        }
    }

    return;
}

void ActiveVar::post_tra(BasicBlock *bb, std::set<BasicBlock *> &visited){
    visited.insert(bb);                       
    for (auto succ : bb->get_succ_basic_blocks()){                                      
        auto is_v = visited.find(succ);
        if (is_v == visited.end())                               
            post_tra(succ, visited);
    }
    bb_int[bb] = bb_list.size(); 
    bb_list.push_back(bb); 
}

void ActiveVar::init(Function *function){
    bb_list.clear();
    bb_int.clear();
    auto entry = function->get_entry_block();
    std::set<BasicBlock *> visited = {}; 
    post_tra(entry, visited); 
    bb_list.reverse();
    bb_def.clear();
    bb_use.clear();
    bb_in.clear();
    bb_out.clear();
    bb_phi.clear();
    for (int i = 0; i <= bb_int[entry]; i++){ 
        bb_def.push_back({});
        bb_use.push_back({});
        bb_in.push_back({});
        bb_out.push_back({});
        bb_phi.push_back({});
    }
    for (auto bb : bb_list){
        std::list<Instruction *> inst = bb->get_instructions();
        for (auto s = inst.rbegin(); s != inst.rend(); s++){
            auto t = *s;
            std::vector<Value *> op = t->get_operands();
            int size = op.size();
            if (!t->is_void()){
                bb_def[bb_int[bb]].insert(t);
                bb_use[bb_int[bb]].erase(t);
            }
            if (t->is_phi()){
                for (auto i = 0; i < size; i += 2)
                    bb_phi[bb_int[bb]].insert(op[i]);
            }
            for (auto p : op){
                if (dynamic_cast<GlobalVariable *>(p) != nullptr || dynamic_cast<Instruction *>(p) != nullptr)
                    bb_use[bb_int[bb]].insert(p);
            }
        }
    }
}

void ActiveVar::ans(Function *function){
    bool change = true;
    while (change){
        change = false;
        for (auto bb : bb_list){
            bb_out[bb_int[bb]].clear();
            for (auto succ : bb->get_succ_basic_blocks()){
                std::set<Value *> set1;
                std::set<Value *> set2;
                for (auto t : succ->get_instructions()){
                    if (!t->is_phi())  break;
                    for (int i = 0; i < t->get_num_operand(); i += 2){
                        if (t->get_operand(i + 1) != bb)
                            set1.insert(t->get_operand(i));
                    }
                }
                for (auto p : set1){
                    if (bb_out[bb_int[succ]].find(p) != bb_out[bb_int[succ]].end() && bb_def[bb_int[succ]].find(p) == bb_def[bb_int[succ]].end()){
                        set2.insert(p);
                        continue;
                    }
                    for (auto u : p->get_use_list()){
                        auto t = dynamic_cast<Instruction *>(u.val_);
                        if (t->get_parent() != succ)  continue;
                        if (!t->is_phi()){  set2.insert(p);break;}
                        else{
                            auto n = u.arg_no_;
                            if (t->get_operand(n + 1) == bb){
                                set2.insert(p);
                                break;
                            }
                        }
                    }
                }
                for (auto k : set2)  set1.erase(k);
                auto l = bb_in[bb_int[succ]];
                for (auto k : set1)   l.erase(k);
                for (auto t : l)  bb_out[bb_int[bb]].insert(t);
            }
            auto m = bb_out[bb_int[bb]];
            for (auto t : bb_def[bb_int[bb]])  m.erase(t);
            for (auto t : bb_use[bb_int[bb]])  m.insert(t);
            for (auto t : bb_phi[bb_int[bb]])  m.insert(t);
            if (m.size() != bb_in[bb_int[bb]].size())  change = true;
            bb_in[bb_int[bb]] = m;
        }
    }
}